#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 128. 最长连续序列.py
@time: 2022/1/29 11:20
@desc: https://leetcode-cn.com/problems/longest-consecutive-sequence/
@解题思路：
    1. 哈希: Ot(n), (比较像Ot(N2)), Os(n)
    2. 排序、暴力
'''


class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        nums_set = set(nums)
        for num in nums:
            if num - 1 not in nums_set:
                cur = num
                cur_ans = 1

                while cur + 1 in nums_set:
                    cur += 1
                    cur_ans += 1

                ans = max(ans, cur_ans)

        return ans

class Solution2(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        nums = set(nums)
        nums = list(nums)
        nums.sort()
        ans = 1
        n = len(nums)
        cur = 1
        for i in range(n-1):
            if nums[i]+1 == nums[i+1]:
                cur += 1
                ans = max(cur, ans)
            else:
                cur = 1
        return ans